// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* Verifica se eh possivel percorrer todos os n vertices */
/* de um grafo comecando pelo vertice x                  */
bool runGraph(vector<int> graph[], int n, int x = 0) {
  if (n == 1)
    return true;

  queue<int> processQueue;    // Fila de processos
  bool counted[MAX];          // Verifica se ja passou por um vertice
  vector<int>::iterator it;
  int count;                  // Conta quantos vertices percorreu
  int currVert;

  for (int i = 0;i < n;i++)   // Seta estado inicial dos vertices
    counted[i] = false;
  counted[x] = true;          // Vertice de origem
  count = 1;

  /* Inicializa a fila de processos adicinando as conecxoes do vertice de origem */
  for (it = graph[x].begin(); it < graph[x].end(); ++it)
    if (!counted[*it]) {
      processQueue.push(*it);
      counted[*it] = true;
      count++;
    }

  /* Processa a fila */
  while (!processQueue.empty()) {
    currVert = processQueue.front();
    processQueue.pop();
    /* Adiciona novos vertices na fila */
    for (it = graph[currVert].begin(); it < graph[currVert].end(); ++it)
      if (!counted[*it]) {
        processQueue.push(*it);
        counted[*it] = true;
        count++;
      }
    /* Verifica se todo o percusso foi feito */
    if (count == n) 
      return true;
  }

  return false;
}

/* Verifica se um grafo eh fortemente conectado */
bool stronglyConnected(vector<int> graph1[], int n) {
  vector<int>::iterator it;
  vector<int> graph2[MAX];      // Versao do grafo com direcao invertida
  bool ret;                     // Variavel de retorno

  /* Inverte o grafo de entrada */
  for (int i = 0;i < n;i++)
    for (it = graph1[i].begin();it < graph1[i].end();++it)
      graph2[*it].push_back(i);

  /* Verifica se a partir de um mesmo ponto eh possivel percorrer */
  /* todo o grafo para os dois tipos de grafo                     */
  ret = runGraph(graph1, n) && runGraph(graph2, n);
  return ret;
}
